{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cherry Pickup II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: cherryPickup"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #摘樱桃 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>rows x cols</code> 的矩阵&nbsp;<code>grid</code>&nbsp;来表示一块樱桃地。 <code>grid</code>&nbsp;中每个格子的数字表示你能获得的樱桃数目。</p>\n",
    "\n",
    "<p>你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 <code>(0,0)</code> 出发，机器人 2 从右上角格子 <code>(0, cols-1)</code> 出发。</p>\n",
    "\n",
    "<p>请你按照如下规则，返回两个机器人能收集的最多樱桃数目：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>从格子&nbsp;<code>(i,j)</code> 出发，机器人可以移动到格子&nbsp;<code>(i+1, j-1)</code>，<code>(i+1, j)</code> 或者&nbsp;<code>(i+1, j+1)</code>&nbsp;。</li>\n",
    "\t<li>当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。</li>\n",
    "\t<li>当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。</li>\n",
    "\t<li>两个机器人在任意时刻都不能移动到 <code>grid</code>&nbsp;外面。</li>\n",
    "\t<li>两个机器人最后都要到达&nbsp;<code>grid</code>&nbsp;最底下一行。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/30/sample_1_1802.png\" style=\"height: 182px; width: 139px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]\n",
    "<strong>输出：</strong>24\n",
    "<strong>解释：</strong>机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。\n",
    "机器人 1 摘的樱桃数目为 (3 + 2 + 5 + 2) = 12 。\n",
    "机器人 2 摘的樱桃数目为 (1 + 5 + 5 + 1) = 12 。\n",
    "樱桃总数为： 12 + 12 = 24 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/30/sample_2_1802.png\" style=\"height: 257px; width: 284px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]\n",
    "<strong>输出：</strong>28\n",
    "<strong>解释：</strong>机器人 1 和机器人 2 的路径在上图中分别用绿色和蓝色表示。\n",
    "机器人 1 摘的樱桃数目为 (1 + 9 + 5 + 2) = 17 。\n",
    "机器人 2 摘的樱桃数目为 (1 + 3 + 4 + 3) = 11 。\n",
    "樱桃总数为： 17 + 11 = 28 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]\n",
    "<strong>输出：</strong>22\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,1],[1,1]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>rows == grid.length</code></li>\n",
    "\t<li><code>cols == grid[i].length</code></li>\n",
    "\t<li><code>2 &lt;= rows, cols &lt;= 70</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 100&nbsp;</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cherry-pickup-ii](https://leetcode.cn/problems/cherry-pickup-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cherry-pickup-ii](https://leetcode.cn/problems/cherry-pickup-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[3,1,1],[2,5,1],[1,5,5],[2,1,1]]', '[[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        nRow, nCol = len(grid), len(grid[0])\n",
    "        dp = [[0]*nCol for _ in range(nCol)]\n",
    "        dp[0][nCol-1] = grid[0][0]+grid[0][nCol-1]\n",
    "        for i in range(1, nRow):\n",
    "            tmp = [[0]*nCol for _ in range(nCol)]\n",
    "            for c1 in range(min(i+1, nCol)):\n",
    "                for c2 in range(nCol-i-1, nCol):\n",
    "                    res = grid[i][c1]+grid[i][c2] if c1!=c2 else grid[i][c1]\n",
    "                    preMax = 0\n",
    "                    for preC1 in [c1-1,c1,c1+1]:\n",
    "                        for preC2 in [c2-1,c2,c2+1]:\n",
    "                            if 0<=preC1<=min(i-1, nCol-1) and max(0,nCol-i)<=preC2<=nCol-1:\n",
    "                                preMax = max(preMax, dp[preC1][preC2])\n",
    "                    tmp[c1][c2] = res+preMax\n",
    "            dp = tmp\n",
    "\n",
    "        res = 0\n",
    "        for l in dp:\n",
    "            for c in l:\n",
    "                if c>res:\n",
    "                    res = c\n",
    "\n",
    "        return res\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        st = Counter()\n",
    "        st[(0, m - 1)] = grid[0][0] + grid[0][m - 1]\n",
    "        for i in range(1, n):\n",
    "            t = Counter()\n",
    "            for j, k in st:\n",
    "                for nj in j -1, j , j + 1:\n",
    "                    for nk in k - 1, k, k + 1:\n",
    "                        if 0 <= nj < m and 0 <= nk < m:\n",
    "                            t[(nj, nk)] = max(t[(nj, nk)], st[(j, k)] + (grid[i][nj] + grid[i][nk]) if nj != nk else grid[i][nj])\n",
    "            st = t\n",
    "        return max(st.values())\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, A: List[List[int]]) -> int:\n",
    "        m, n = len(A), len(A[0])\n",
    "        dp = [[[float(\"-inf\")] * n for j in range(n)] for i in range(m)]\n",
    "        dp[0][0][n - 1] = A[0][0] + A[0][n - 1]\n",
    "        for i in range(1, m):\n",
    "            for j in range(min(n, i + 1)):\n",
    "                for k in range(max(j + 1, n - i - 1), n):\n",
    "                    s = A[i][j] + A[i][k]\n",
    "                    for dj in range(-1, 2):\n",
    "                        j2 = j + dj\n",
    "                        if j2 < 0 or j2 >= n: continue\n",
    "                        for dk in range(-1, 2):\n",
    "                            k2 = k + dk\n",
    "                            if k2 < 0 or k2 >= n: continue\n",
    "                            if j2 < k2:\n",
    "                                dp[i][j][k] = max(dp[i][j][k], s + dp[i - 1][j2][k2])\n",
    "        #print(dp)\n",
    "        return  max(e for row in dp[-1] for e in row)          \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        dp = [[[-1] * n for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0][n-1] = grid[0][0] + grid[0][n-1]\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    best = -1\n",
    "                    for dj1 in [j - 1, j, j + 1]:\n",
    "                        for dj2 in [k - 1, k, k + 1]:\n",
    "                            if 0 <= dj1 < n and 0 <= dj2 < n:\n",
    "                                best = max(best, dp[i - 1][dj1][dj2])\n",
    "                    if best==-1:\n",
    "                        dp[i][j][k]=-1\n",
    "                    else:\n",
    "                        dp[i][j][k]=best+grid[i][j]+(j!=k)*grid[i][k]\n",
    "\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans=max(ans,dp[m-1][i][j])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        *dires, = itertools.product([-1, 0, 1], [-1, 0, 1])\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0][n - 1] = grid[0][0] + grid[0][n - 1]\n",
    "        for i in range(m - 1):\n",
    "            for j1 in range(0, min(i + 1, n), 1):\n",
    "                for j2 in range(n - 1, max(n - i - 2, -1), -1):\n",
    "                    for d1, d2 in dires:\n",
    "                        nj1, nj2 = j1 + d1, j2 + d2\n",
    "                        if 0 <= nj1 < n and 0 <= nj2 < n:\n",
    "                            dp[i + 1][nj1][nj2] = max(dp[i + 1][nj1][nj2], dp[i][j1][j2] + grid[i + 1][nj1] + (nj1 != nj2) * grid[i + 1][nj2])\n",
    "        # print(dp[1])\n",
    "        return max(max(row) for row in dp[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[]\n",
    "        for i in range(m):  #dp[i][j][k]:位于第i行，左机器人在j列，右在k列（0-n-1）\n",
    "            dp.append([])\n",
    "            for j in range(n):\n",
    "                dp[-1].append([])\n",
    "                for k in range(n):\n",
    "                    dp[-1][-1].append(0)\n",
    "        #initialize\n",
    "        dp[0][0][n-1]=grid[0][0]+grid[0][n-1]\n",
    "        for row in range(1,m):\n",
    "            for c1 in range(n):\n",
    "                for c2 in range(n):\n",
    "                    if c1<=row and c2>=n-1-row:  #不能走太多\n",
    "                        t=0\n",
    "                        if c1>0 and c2>0:\n",
    "                            t=max(dp[row-1][c1-1][c2-1],t)\n",
    "                        if c1>0:\n",
    "                            t=max(dp[row-1][c1-1][c2],t)\n",
    "                        if c1>0 and c2<n-1:\n",
    "                            t=max(dp[row-1][c1-1][c2+1],t)\n",
    "                        if c2>1:\n",
    "                            t=max(dp[row-1][c1][c2-1],t)\n",
    "                        if 1:\n",
    "                            t=max(dp[row-1][c1][c2],t)\n",
    "                        if  c2<n-1:\n",
    "                            t=max(dp[row-1][c1][c2+1],t)\n",
    "                        if c1<n-1 and c2>1:\n",
    "                            t=max(dp[row-1][c1+1][c2-1],t)\n",
    "                        if c1<n-1 :\n",
    "                            t=max(dp[row-1][c1+1][c2],t)\n",
    "                        if c1<n-1 and c2<n-1:\n",
    "                            t=max(dp[row-1][c1+1][c2+1],t)\n",
    "                          \n",
    "                        if c1!=c2:\n",
    "                            dp[row][c1][c2]=t+grid[row][c1]+grid[row][c2]\n",
    "                        else:\n",
    "                            dp[row][c1][c2]=t+grid[row][c1]\n",
    "        cur=0\n",
    "        lst=dp[-1]\n",
    "        for i in lst:\n",
    "            cur=max(cur,max(i))\n",
    "        return cur\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp = [[[0 for _ in range(n)] for _ in range(n)]for _ in range(m)]\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                dp[-1][i][j] = grid[m-1][i] + grid[m-1][j]\n",
    "        for i in range(m-2,-1,-1):\n",
    "            for j in range(n-1):\n",
    "                for k in range(j+1,n):\n",
    "                    dp[i][j][k] = max(dp[i+1][a][b] for a in range(max(j-1,0),j+2,1) for b in range(max(k-1,a+1),min(k+2,n),1))+ grid[i][j] + grid[i][k]\n",
    "        return dp[0][0][n-1]\n",
    "                        \n",
    "                        \n",
    "                        \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        dx = [-1, 0, 1]\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        N = 75\n",
    "        dp = [[[0] * N for _ in range(m)] for _ in range(n)]\n",
    "        dp[0][0][m - 1] = grid[0][0] + grid[0][m - 1]\n",
    "        for i in range(1, n):\n",
    "            for j1 in range(m):\n",
    "                if j1 > i:\n",
    "                    break\n",
    "                for j2 in range(j1 + 1, m):\n",
    "                    if j2 < m - 1 - i:\n",
    "                        continue\n",
    "                    for d1 in range(3):\n",
    "                        for d2 in range(3):\n",
    "                            p1, p2 = j1 + dx[d1], j2 + dx[d2]\n",
    "                            if p1 < 0 or p1 >= m or p2 < 0 or p2 >= m:\n",
    "                                continue\n",
    "                            dp[i][j1][j2] = max(dp[i][j1][j2], dp[i - 1][p1][p2] + grid[i][j1] + grid[i][j2])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(i + 1, m):\n",
    "                ans = max(ans, dp[n - 1][i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp = [ [ [-10**9]*n  for _ in range(n)] for _ in range(m)] \n",
    "\n",
    "        dp[0][0][-1] = grid[0][0] + grid[0][-1]\n",
    "        directions = [ ]\n",
    "        for i in range(-1,2):\n",
    "            for j in range(-1,2):\n",
    "                directions.append((i,j))\n",
    "\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if dp[i-1][j][k] >= 0:\n",
    "                        for dx,dy in directions:\n",
    "                            nx ,ny = j+dx,k+dy\n",
    "                            if nx>=0 and nx<n and ny>=0 and ny<n:\n",
    "                                if nx==ny:\n",
    "                                    tmp = dp[i-1][j][k] + grid[i][nx] \n",
    "                                else:\n",
    "                                    tmp = dp[i-1][j][k] + grid[i][nx] + grid[i][ny]\n",
    "                                dp[i][nx][ny] = max( dp[i][nx][ny] ,tmp )\n",
    "        ans = dp[-1][0][0]\n",
    "        for j in range(n):\n",
    "            for k in range(n):\n",
    "                ans = max(ans,dp[-1][j][k]) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, nums: List[List[int]]) -> int:\n",
    "        n = len(nums)\n",
    "        m = len(nums[0])\n",
    "        f = [[[0] * m for _ in range(m)] for _ in range(n)]\n",
    "        f[0][0][m - 1] = nums[0][0] + nums[0][m - 1]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                for k in range(m):\n",
    "                    if j > i or k < m - i - 1:\n",
    "                        continue\n",
    "                    for u1 in (-1, 0, 1):\n",
    "                        for u2 in (-1, 0, 1):\n",
    "                            a = j + u1\n",
    "                            b = k + u2\n",
    "                            if 0 <= a < m and 0 <= b < m: \n",
    "                                f[i][j][k] = max(f[i - 1][a][b], f[i][j][k])\n",
    "                    \n",
    "                    if a == b:\n",
    "                        f[i][j][k] += nums[i][j]\n",
    "                    else:\n",
    "                        f[i][j][k] += nums[i][j] + nums[i][k]\n",
    "        res = 0\n",
    "        for j in range(m):\n",
    "            for k in range(m):\n",
    "                res = max(res, f[n - 1][j][k])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        # 获取矩阵的行数和列数\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        # 初始化一个三维数组 dp[i][j][k] 来表示第 i 行时，机器人 1 在第 j 列，机器人 2 在第 k 列时能收集到的最多樱桃数\n",
    "        dp = [[[0 for _ in range(m)] for _ in range(m)] for _ in range(n)]\n",
    "        # 初始化第 0 行\n",
    "        if m != 1: \n",
    "            dp[0][0][-1] = grid[0][0] + grid[0][-1]\n",
    "        else:\n",
    "            dp[0][0][-1] = grid[0][0]\n",
    "        # 遍历每一行\n",
    "        for i in range(1, n):\n",
    "            # 遍历每一列\n",
    "            for j in range(min(i+1, m)):\n",
    "                for k in range(max(m-1-i, j+1), m):\n",
    "                    # 遍历上一行可能移动到的列数\n",
    "                    for p in [-1, 0, 1]:\n",
    "                        for q in [-1, 0, 1]:\n",
    "                            # 计算上一行的列数\n",
    "                            x = j + p\n",
    "                            y = k + q\n",
    "                            # 如果上一行的列数在范围内\n",
    "                            if 0 <= x < m and 0 <= y < m:\n",
    "                                # 更新当前状态为 grid[i][j] + grid[i][k] 加上 dp[i-1][x][y] 的最大值\n",
    "                                # 如果 j 和 k 相等，则只加一次 grid[i][j]\n",
    "                                if j == k:\n",
    "                                    dp[i][j][k] = max(dp[i][j][k], grid[i][j] + dp[i-1][x][y])\n",
    "                                else:\n",
    "                                    dp[i][j][k] = max(dp[i][j][k], grid[i][j] + grid[i][k] + dp[i-1][x][y])\n",
    "        # 初始化答案为 0\n",
    "        ans = 0\n",
    "        # 从 dp[n-1][j][k] 中找到最大值作为答案\n",
    "        for j in range(m):\n",
    "            for k in range(m):\n",
    "                ans = max(ans, dp[n-1][j][k])\n",
    "        # 返回答案\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        # dp[i][j][k] 代表 机器人1在(i, j), 机器人2在(i, k)位置时候的最大值\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        dp = [[[0] * col for _ in range(col)] for __ in range(row)]\n",
    "        dp[0][0][-1] = grid[0][0] + grid[0][-1]\n",
    "        visited = {(0, col-1)}\n",
    "        for i in range(1, row):\n",
    "            new_visited = set()\n",
    "            for j, k in visited:\n",
    "                for nxt_j, nxt_k in itertools.product([j-1, j, j+1], [k-1, k, k+1]):\n",
    "                    if 0 <= nxt_j < col and 0 <= nxt_k < col:\n",
    "                        new_visited.add((nxt_j, nxt_k))\n",
    "                        if nxt_j != nxt_k:\n",
    "                            dp[i][nxt_j][nxt_k] = max(dp[i][nxt_j][nxt_k], dp[i-1][j][k] + grid[i][nxt_j] + grid[i][nxt_k])\n",
    "                        else:\n",
    "                            dp[i][nxt_j][nxt_k] = max(dp[i][nxt_j][nxt_k], dp[i-1][j][k] + grid[i][nxt_j])\n",
    "            visited = new_visited\n",
    "        \n",
    "        ans = 0\n",
    "        for j in range(col):\n",
    "            for k in range(col):\n",
    "                ans = max(ans, dp[-1][j][k])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        dp = [[[0] * n for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "         # initial last row\n",
    "        for y1 in range(n):\n",
    "            for y2 in range(n):\n",
    "                dp[m-1][y1][y2] = grid[m-1][y1] + grid[m-1][y2] if y1 != y2 else grid[m-1][y2] # if overlap, only count one time\n",
    "\n",
    "        for x in range(m-2, -1, -1):\n",
    "            for y1 in range(n):\n",
    "                for y2 in range(n):\n",
    "                    cur = grid[x][y1] + grid[x][y2] if y1!= y2 else grid[x][y2]\n",
    "\n",
    "                    max_prev = 0\n",
    "                    for dy1 in range(-1, 2):\n",
    "                        for dy2 in range(-1, 2):\n",
    "                            cur_y1 = y1 + dy1\n",
    "                            cur_y2 = y2 + dy2 \n",
    "\n",
    "                            if 0<=cur_y1<n and 0<=cur_y2<n:\n",
    "                                max_prev = max(max_prev, dp[x + 1][cur_y1][cur_y2])\n",
    "\n",
    "                    dp[x][y1][y2] = max_prev + cur\n",
    "        \n",
    "        return dp[0][0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        h = len(grid)\n",
    "        w = len(grid[0])\n",
    "        dp = []\n",
    "        bias = [-1, 0, 1]\n",
    "        for x in range(h+1):\n",
    "            dp.append([[0 for _ in range(w)] for _ in range(w)])\n",
    "        for x in range(h-1, -1, -1):\n",
    "            for y0 in range(w):\n",
    "                for y1 in range(w):\n",
    "                    score = grid[x][y0] if y0 == y1 else grid[x][y0] + grid[x][y1]\n",
    "                    for y0_b in bias:\n",
    "                        y0_n = y0 + y0_b\n",
    "                        if y0_n < 0 or y0_n >=w:\n",
    "                            continue\n",
    "                        for y1_b in bias:\n",
    "                            y1_n = y1 + y1_b\n",
    "                            if y1_n < 0 or y1_n >= w:\n",
    "                                continue\n",
    "                            dp[x][y0][y1] = max(dp[x][y0][y1], dp[x+1][y0_n][y1_n]+score)\n",
    "        return dp[0][0][w-1]\n",
    "                            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from typing import List, Tuple\n",
    "from collections import deque\n",
    "INF = int(1e18)\n",
    "class Edge:\n",
    "    __slots__ = (\"fromV\", \"toV\", \"cap\", \"cost\", \"flow\")\n",
    "    def __init__(self, fromV: int, toV: int, cap: int, cost: int, flow: int) -> None:\n",
    "        self.fromV = fromV\n",
    "        self.toV = toV\n",
    "        self.cap = cap\n",
    "        self.cost = cost\n",
    "        self.flow = flow\n",
    "class MinCostMaxFlowEK:\n",
    "    \"\"\"最小费用流的复杂度为流量*spfa的复杂度\"\"\"\n",
    "    __slots__ = (\"_n\", \"_start\", \"_end\", \"_edges\", \"_reGraph\", \"_dist\", \"_pre\", \"_flow\")\n",
    "    def __init__(self, n: int, start: int, end: int):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            n (int): 包含虚拟点在内的总点数\n",
    "            start (int): (虚拟)源点\n",
    "            end (int): (虚拟)汇点\n",
    "        \"\"\"\n",
    "        assert 0 <= start < n and 0 <= end < n\n",
    "        self._n = n\n",
    "        self._start = start\n",
    "        self._end = end\n",
    "        self._edges: List[\"Edge\"] = []\n",
    "        self._reGraph: List[List[int]] = [[] for _ in range(n)]  # 残量图存储的是边的下标\n",
    "\n",
    "        self._dist = [INF] * n\n",
    "        self._flow = [0] * n\n",
    "        self._pre = [-1] * n\n",
    "    def addEdge(self, fromV: int, toV: int, cap: int, cost: int) -> None:\n",
    "        \"\"\"原边索引为i 反向边索引为i^1\"\"\"\n",
    "        self._edges.append(Edge(fromV, toV, cap, cost, 0))\n",
    "        self._edges.append(Edge(toV, fromV, 0, -cost, 0))\n",
    "        len_ = len(self._edges)\n",
    "        self._reGraph[fromV].append(len_ - 2)\n",
    "        self._reGraph[toV].append(len_ - 1)\n",
    "    def work(self) -> Tuple[int, int]:\n",
    "        \"\"\"\n",
    "        Returns:\n",
    "            Tuple[int, int]: [最大流,最小费用]\n",
    "        \"\"\"\n",
    "        maxFlow, minCost = 0, 0\n",
    "        while self._spfa():\n",
    "            delta = self._flow[self._end]\n",
    "            minCost += delta * self._dist[self._end]\n",
    "            maxFlow += delta\n",
    "            cur = self._end\n",
    "            while cur != self._start:\n",
    "                edgeIndex = self._pre[cur]\n",
    "                self._edges[edgeIndex].flow += delta\n",
    "                self._edges[edgeIndex ^ 1].flow -= delta\n",
    "                cur = self._edges[edgeIndex].fromV\n",
    "        return maxFlow, minCost\n",
    "    def _spfa(self) -> bool:\n",
    "        \"\"\"spfa沿着最短路寻找增广路径  有负cost的边不能用dijkstra\"\"\"\n",
    "        n, start, end, edges, reGraph = (\n",
    "            self._n,\n",
    "            self._start,\n",
    "            self._end,\n",
    "            self._edges,\n",
    "            self._reGraph,\n",
    "        )\n",
    "        self._flow = flow = [0] * n\n",
    "        self._pre = pre = [-1] * n\n",
    "        self._dist = dist = [INF] * n\n",
    "        dist[start] = 0\n",
    "        flow[start] = INF\n",
    "        inQueue = [False] * n\n",
    "        inQueue[start] = True\n",
    "        queue = deque([start])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            inQueue[cur] = False\n",
    "            for edgeIndex in reGraph[cur]:\n",
    "                edge = edges[edgeIndex]\n",
    "                cost, remain, next = edge.cost, edge.cap - edge.flow, edge.toV\n",
    "                if remain > 0 and dist[cur] + cost < dist[next]:\n",
    "                    dist[next] = dist[cur] + cost\n",
    "                    pre[next] = edgeIndex\n",
    "                    flow[next] = remain if remain < flow[cur] else flow[cur]\n",
    "                    if not inQueue[next]:\n",
    "                        inQueue[next] = True\n",
    "                        if queue and dist[queue[0]] > dist[next]:\n",
    "                            queue.appendleft(next)\n",
    "                        else:\n",
    "                            queue.append(next)\n",
    "        return pre[end] != -1\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        st=2*m*n+5\n",
    "        ed=st+1\n",
    "        mf=MinCostMaxFlowEK(2*m*n+10,st,ed)\n",
    "        mf.addEdge(st,0,1,0)\n",
    "        mf.addEdge(st,n-1,1,0)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mf.addEdge(i*n+j,i*n+j+m*n,1,-grid[i][j])\n",
    "                mf.addEdge(i*n+j,i*n+j+m*n,1,0)\n",
    "                for ni,nj in [(i+1,j-1),(i+1,j),(i+1,j+1)]:\n",
    "                    if 0<=ni<m and 0<=nj<n:\n",
    "                        mf.addEdge(i*n+j+m*n,ni*n+nj,2,0)\n",
    "                if i==m-1:\n",
    "                    mf.addEdge(i*n+j+m*n,ed,2,0)\n",
    "        return -mf.work()[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        memo = [[[-1]*n for _ in range(n)] for _ in range(m)]\n",
    "        def topdown(x, y1, y2):\n",
    "            if x >= m:\n",
    "                return 0\n",
    "            if memo[x][y1][y2] > -1:\n",
    "                return memo[x][y1][y2]\n",
    "            ans = grid[x][y1]\n",
    "            if y1 != y2:\n",
    "                ans += grid[x][y2]\n",
    "            temp = 0\n",
    "            for a in [-1, 0, 1]:\n",
    "                for b in [-1, 0, 1]:\n",
    "                    ny1, ny2 = y1+a, y2+b\n",
    "                    if 0<=ny1<n and 0<=ny2<n:\n",
    "                        temp = max(temp, topdown(x+1, ny1, ny2))\n",
    "            ans += temp\n",
    "            memo[x][y1][y2] = ans\n",
    "            return ans\n",
    "        return topdown(0, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        # @cache\n",
    "        # def dfs(i,j1,j2):\n",
    "        #     if i == 0:\n",
    "        #         if j1 == 0 and j2 == n - 1:\n",
    "        #             return grid[i][j1] + grid[i][j2]\n",
    "        #         return -inf\n",
    "        #     t = grid[i][j1] + (grid[i][j2] if j1 != j2 else 0)\n",
    "        #     ans = -inf\n",
    "        #     for x in (j1 - 1,j1,j1 + 1):\n",
    "        #         for y in (j2 - 1,j2,j2 + 1):\n",
    "        #             if 0 <= x < n and 0 <= y < n:\n",
    "        #                 ans = max(ans,dfs(i - 1,x,y))\n",
    "        #     return ans + t\n",
    "        \n",
    "        # return max(dfs(m - 1,j1,j2) for j1 in range(n) for j2 in range(n))\n",
    "\n",
    "        f = [[[-inf]*(n + 1) for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        f[1][1][n] = grid[0][0] + grid[0][-1]\n",
    "        for i in range(2,m + 1):\n",
    "            for j1 in range(1,n + 1):\n",
    "                for j2 in range(1,n + 1):\n",
    "                    t = grid[i-1][j1 - 1] + (grid[i - 1][j2 - 1] if j1 != j2 else 0)\n",
    "                    f[i][j1][j2] = max(f[i - 1][j1 + x][j2 + y] for x in (-1,0,1) for y in (-1,0,1) if 1 <= j1 + x <= n and 1 <= j2 + y <= n) + t\n",
    "        return max(f[-1][x][y] for x in range(1,n + 1) for y in range(1,n + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        dp = [defaultdict(lambda: 0) for _ in range(n)]\n",
    "        dp[0][(0, m - 1)] = grid[0][0] + grid[0][m - 1]\n",
    "        _pos = [-1, 0, 1]\n",
    "\n",
    "        def check(p, _p):\n",
    "            p += _p\n",
    "            return p >= 0 and p < m\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            for (x, y), val in dp[i].items():\n",
    "                for it in _pos:\n",
    "                    if check(x, it):\n",
    "                        for jt in _pos:\n",
    "                            if check(y, jt):\n",
    "                                if x + it == y + jt:\n",
    "                                    dp[i + 1][(x + it, y + jt)] = max(\n",
    "                                        dp[i + 1][(x + it, y + jt)],\n",
    "                                        val + grid[i + 1][x + it],\n",
    "                                    )\n",
    "                                else:\n",
    "                                    dp[i + 1][(x + it, y + jt)] = max(\n",
    "                                        dp[i + 1][(x + it, y + jt)],\n",
    "                                        val + grid[i + 1][x + it] + grid[i + 1][y + jt],\n",
    "                                    )\n",
    "        return max(dp[n - 1].values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        inf = 10 ** 9\n",
    "        dp = [{} for _ in range(m)]\n",
    "        dp[0][(0, n-1)] = grid[0][0]+grid[0][-1]\n",
    "        for r in range(1, m):\n",
    "            for c1 in range(min(r, n-1) + 1):\n",
    "                for c2 in range(n-1, max(0, n-1-r)-1, -1):\n",
    "                    if c1 == c2:\n",
    "                        add = grid[r][c1]\n",
    "                    else:\n",
    "                        add = grid[r][c1] + grid[r][c2]\n",
    "                    dp[r][(c1, c2)] = max(\n",
    "                        dp[r-1].get((c1 - 1, c2 - 1), -inf),\n",
    "                        dp[r-1].get((c1 - 1, c2), -inf),\n",
    "                        dp[r-1].get((c1 - 1, c2 + 1), -inf),\n",
    "                        dp[r-1].get((c1, c2 - 1), -inf),\n",
    "                        dp[r-1].get((c1, c2), -inf),\n",
    "                        dp[r-1].get((c1, c2 + 1), -inf),\n",
    "                        dp[r-1].get((c1 + 1, c2 - 1), -inf),\n",
    "                        dp[r-1].get((c1 + 1, c2), -inf),\n",
    "                        dp[r-1].get((c1 + 1, c2 + 1), -inf)\n",
    "                    ) + add\n",
    "        return max(dp[m-1].values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        # max cherries starting from (i, j) and (i, k)\n",
    "        from functools import lru_cache\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int, j: int, k: int) -> int:\n",
    "            ans = (grid[i][j] + grid[i][k]) if j != k else grid[i][j]\n",
    "            if i == m - 1:\n",
    "                return ans\n",
    "            return ans + max(dp(i + 1, j2, k2) for j2 in [j - 1, j, j + 1] for k2 in [k - 1, k, k + 1] if 0 <= j2 < n and 0 <= k2 < n)\n",
    "        \n",
    "        return dp(0, 0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dpf(x1: int, y1: int, x2: int, y2: int) -> int:\n",
    "            if not (0 <= x1 < len(grid) and 0 <= x2 < len(grid) and 0 <= y1 < len(grid[0]) and 0 <= y2 < len(grid[0])):\n",
    "                return 0\n",
    "            if x1 == len(grid) - 1:\n",
    "                if y1 == y2:\n",
    "                    return grid[x1][y1]\n",
    "                else:\n",
    "                    return grid[x1][y1] + grid[x2][y2]\n",
    "            maxnum = max([dpf(x1 + 1, y1 + p[0], x2 + 1, y2 + p[1]) for p in itertools.product([-1, 0, 1], [-1, 0, 1])])\n",
    "            if x1 == x2 and y1 == y2:\n",
    "                maxnum += grid[x1][y1]\n",
    "            else:\n",
    "                maxnum += grid[x1][y1] + grid[x2][y2]\n",
    "            return maxnum\n",
    "\n",
    "        return dpf(0, 0, 0, len(grid[0]) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[-inf for _ in range(n)] for _ in range(n)] for _ in range(m)]\n",
    "        f[0][0][n-1] = grid[0][0] + grid[0][n-1]\n",
    "\n",
    "        for row in range(1, m):\n",
    "            for j1 in range(n):\n",
    "                for j2 in range(n):\n",
    "                    increment = grid[row][j1] + grid[row][j2]\n",
    "                    if j1 == j2:\n",
    "                        increment -= grid[row][j2]\n",
    "                    for diff_1, diff_2 in product(range(-1, 2), range(-1, 2)):\n",
    "                        last_j1 = j1 + diff_1\n",
    "                        last_j2 = j2 + diff_2\n",
    "                        if 0 <= last_j1 < n and 0 <= last_j2 < n:\n",
    "                            f[row][j1][j2] = max(f[row][j1][j2], f[row-1][last_j1][last_j2] + increment)\n",
    "        \n",
    "\n",
    "        return max([max(f[-1][col]) for col in range(n)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[[-float('inf') for i in range(n)] for j in range(n)] for k in range(m)]\n",
    "        dp[0][0][n-1]=grid[0][0]+grid[0][n-1]\n",
    "        result=0\n",
    "        for i in range(1,m):\n",
    "            for j1 in range(n):\n",
    "                for j2 in range(n):\n",
    "                    if j1==j2:\n",
    "                        res=grid[i][j1]\n",
    "                    else:\n",
    "                        res=grid[i][j1]+grid[i][j2]\n",
    "                    for p1 in (0,-1,1):\n",
    "                        for p2 in (0,-1,1):\n",
    "                            if 0<=j1+p1<n and 0<=j2+p2<n:\n",
    "                                dp[i][j1][j2]=max(dp[i-1][j1+p1][j2+p2]+res,dp[i][j1][j2])\n",
    "                    result=max(result, dp[i][j1][j2])\n",
    "        return result\n",
    "\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[[-float('inf') for i in range(n)] for j in range(n)] for k in range(m)]\n",
    "        dp[0][0][n-1]=grid[0][0]+grid[0][n-1]\n",
    "        directions=[0,-1,1]\n",
    "        for i in range(1,m):\n",
    "            for j1 in range(n):\n",
    "                for j2 in range(n):\n",
    "                    if j1==j2:\n",
    "                        res=grid[i][j1]\n",
    "                    else:\n",
    "                        res=grid[i][j1]+grid[i][j2]\n",
    "                    for p1 in directions:\n",
    "                        for p2 in directions:\n",
    "                            if 0<=j1+p1<n and 0<=j2+p2<n:\n",
    "                                dp[i][j1][j2]=max(dp[i-1][j1+p1][j2+p2]+res,dp[i][j1][j2])\n",
    "        result=0\n",
    "        for j1 in range(n):\n",
    "            for j2 in range(n):\n",
    "                result=max(result, dp[m-1][j1][j2])\n",
    "        return result\n",
    "\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        row = len(grid)\n",
    "        col = len(grid[0])\n",
    "        Z = list(product((-1, 0, 1), repeat = 2))\n",
    "        @lru_cache(None)\n",
    "        def D(i, l, r):\n",
    "            if i == row - 1:\n",
    "                return 0\n",
    "            d = 0\n",
    "            for dl, dr in Z:\n",
    "                nl, nr = l + dl, r + dr\n",
    "                if 0 <= nl < nr <= col - 1:\n",
    "                    d = max(d, D(i + 1, nl, nr) + grid[i + 1][nl] + grid[i + 1][nr])\n",
    "            return d\n",
    "        return D(0, 0, col - 1) + grid[0][0] + grid[0][col - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j,k):\n",
    "            if i == m - 1:\n",
    "                return grid[i][j] + grid[i][k]\n",
    "            return max(dfs(i+1,a,b) for a in range(max(j-1,0),j+2,1) for b in range(max(a+1,k-1),min(k+2,n),1)) + grid[i][j] + grid[i][k]\n",
    "        return dfs(0,0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        *dires, = itertools.product([-1, 0, 1], [-1, 0, 1])\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, j1, j2):\n",
    "            if i == m - 1:\n",
    "                return grid[i][j1] + (j1 != j2) * grid[i][j2]\n",
    "            res = 0\n",
    "            for d1, d2 in dires:\n",
    "                nj1, nj2 = j1 + d1, j2 + d2\n",
    "                if 0 <= nj1 <= nj2 < n:\n",
    "                    res = max(res, dfs(i + 1, nj1, nj2))\n",
    "            return res + grid[i][j1] + (j1 != j2) * grid[i][j2]\n",
    "\n",
    "        return dfs(0, 0, n - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y1, y2):\n",
    "            res = grid[x][y1] + grid[x][y2]\n",
    "            if y1 == y2:\n",
    "                res -= grid[x][y1]\n",
    "            if x == m-1:\n",
    "                return res\n",
    "            nex1 = [[x+1,  y1], [x+1, y1-1], [x+1, y1+1]]\n",
    "            nex1 = [[i, j] for i, j in nex1 if 0<=i<m and 0<=j<n]\n",
    "            nex2 = [[x+1,  y2], [x+1, y2-1], [x+1, y2+1]]\n",
    "            nex2 = [[i, j] for i, j in nex2 if 0<=i<m and 0<=j<n]\n",
    "            add = 0\n",
    "            for i1, j1 in nex1:\n",
    "                for i2, j2 in nex2:\n",
    "                    cur = dfs(i1, j1, j2)\n",
    "                    if cur > add:\n",
    "                        add = cur\n",
    "            return res + add\n",
    "\n",
    "        return dfs(0, 0, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        d = [[[-1 for _ in range(n)] for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        def dfs(r, r1, r2):\n",
    "            cur = 0\n",
    "            if r == -1:\n",
    "                return 0\n",
    "            if d[r][r1][r2] != -1:\n",
    "                return d[r][r1][r2]\n",
    "            cur = grid[r][r1] + grid[r][r2]\n",
    "            if r1 == r2:\n",
    "                cur //= 2\n",
    "            l = product(range(max(r1 - 1, 0), min(r1 + 2, n)), range(max(r2 - 1, 0), min(r2 + 2, n)))\n",
    "\n",
    "            t = -1000000000\n",
    "            for c1, c2 in l:\n",
    "                if r == 1:\n",
    "                    if (c1, c2) != (0, n - 1):  continue\n",
    "                t = max(t, dfs(r - 1, c1, c2))\n",
    "            cur += t\n",
    "            d[r][r1][r2] = cur\n",
    "            return cur\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                ans = max(dfs(m - 1, i, j), ans)\n",
    "        return ans\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y1, y2):\n",
    "            if x == m:\n",
    "                return 0\n",
    "            \n",
    "            res = 0\n",
    "            v = grid[x][y1] + grid[x][y2] if y1 != y2 else grid[x][y1]\n",
    "            for d1 in (-1, 0, 1):\n",
    "                for d2 in (-1, 0, 1):\n",
    "                    a, b = y1 + d1, y2 + d2\n",
    "                    if 0 <= a < n and 0 <= b < n:\n",
    "                        res = max(res, v + dfs(x + 1, a, b))\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, 0, n - 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        row,col=len(grid),len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(x1,y1,x2,y2):\n",
    "            nonlocal row,col\n",
    "            if x1==x2 and y1==y2:\n",
    "                ret=grid[x1][y1]\n",
    "            else:\n",
    "                ret=grid[x1][y1]+grid[x2][y2]\n",
    "            dif=0\n",
    "            for dx,dy in [[1,-1],[1,0],[1,1]]:\n",
    "                nx1,ny1=x1+dx,y1+dy\n",
    "                if 0<=nx1<row and 0<=ny1<col:\n",
    "                    for dxx,dyy in [[1,-1],[1,0],[1,1]]:\n",
    "                        nx2,ny2=x2+dxx,y2+dyy\n",
    "                        if 0<=nx2<row and 0<=ny2<col:\n",
    "                            dif=max(dfs(nx1,ny1,nx2,ny2),dif)\n",
    "            return ret+dif\n",
    "        return max(dfs(0,0,0,col-1),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        res = self.cherryPickupHelper(grid, (0, 0), (0, len(grid[0])-1), dic)\n",
    "        # print(dic)\n",
    "\n",
    "        return res\n",
    "\n",
    "    def cherryPickupHelper(self, grid, pos1, pos2, dic):\n",
    "        if pos1[0] >= len(grid):\n",
    "            return -999\n",
    "\n",
    "        if pos1[1] < 0 or pos1[1] >= len(grid[0]) or pos2[1] < 0 or pos2[1] >= len(grid[0]):\n",
    "            return -999\n",
    "\n",
    "        if pos1[0] == len(grid) - 1:\n",
    "            if pos1[0] == pos2[0] and pos1[1] == pos2[1]:\n",
    "                dic[self.pos_to_str(pos1, pos2)] = 0\n",
    "                return 0\n",
    "\n",
    "            else:\n",
    "                dic[self.pos_to_str(pos1, pos2)] = grid[pos1[0]][pos1[1]] + grid[pos2[0]][pos2[1]]\n",
    "                return dic[self.pos_to_str(pos1, pos2)]\n",
    "\n",
    "\n",
    "        if self.pos_to_str(pos1, pos2) in dic:\n",
    "            return dic[self.pos_to_str(pos1, pos2)]\n",
    "\n",
    "        max_val = -1\n",
    "        for i in range(-1, 2):\n",
    "            for j in range(-1, 2):\n",
    "                # print(i, j, pos1, pos2, (pos1[0] + 1, pos1[1] + i), (pos2[0] + 1, pos2[1] + j))\n",
    "                res = self.cherryPickupHelper(grid, (pos1[0] + 1, pos1[1] + i), (pos2[0] + 1, pos2[1] + j), dic)\n",
    "                if res > max_val:\n",
    "                    max_val = res\n",
    "\n",
    "\n",
    "        if pos1[0] == pos2[0] and pos1[1] == pos2[1]:\n",
    "            dic[self.pos_to_str(pos1, pos2)] = max_val\n",
    "        else:\n",
    "            dic[self.pos_to_str(pos1, pos2)] = max_val + grid[pos1[0]][pos1[1]] + grid[pos2[0]][pos2[1]]\n",
    "        # print(pos1, pos2, dic[self.pos_to_str(pos1, pos2)])\n",
    "        return dic[self.pos_to_str(pos1, pos2)]\n",
    "            \n",
    "\n",
    "    def pos_to_str(self, pos1, pos2):\n",
    "        return str(pos1) + str(pos2)\n",
    "        # return pos1[0] * 1000 + pos1[1] * 100 + pos2[0] * 10 + pos2[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, g: List[List[int]]) -> int:\n",
    "        m, n = len(g), len(g[0])\n",
    "        @cache\n",
    "        def dfs(x, y1, y2):\n",
    "            if y1 < 0 or y1 >= n or y2 < 0 or y2 >= n: return 0\n",
    "            if x == m - 1: return g[x][y1] + (g[x][y2] if y1 != y2 else 0)\n",
    "            return g[x][y1] + (g[x][y2] if y1 != y2 else 0)\\\n",
    "            + max(dfs(x + 1, y1 + i, y2 + j) for i in range(-1, 2) for j in range(-1, 2))\n",
    "        return dfs(0, 0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "\n",
    "        @cache\n",
    "        def dp(col1: int, col2: int, row: int) -> int:\n",
    "            if col1 < 0 or col2 >= cols or row >= rows:\n",
    "                return 0\n",
    "            return grid[row][col1] + (grid[row][col2] if col1 != col2 else 0) \\\n",
    "                   + max(dp(min(i1, i2), max(i1, i2), row + 1) for i1 in range(col1 - 1, col1 + 2) for i2 in range(col2 - 1, col2 + 2))\n",
    "\n",
    "        return dp(0, cols - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        cache ={}\n",
    "        height =len(grid)\n",
    "        width = len(grid[0])\n",
    "        def dp_helper(j,x1,x2):\n",
    "            if j == height:\n",
    "                return 0\n",
    "            if (j,x1,x2) in cache:\n",
    "                return cache[(j,x1,x2)]\n",
    "            \n",
    "            next_x1 = [a for a in [x1-1,x1,x1+1] if 0<=a<=width]\n",
    "            next_x2 = [b for b in [x2-1,x2,x2+1] if 0<=b<=width]\n",
    "\n",
    "            \n",
    "            next_pick = max([\n",
    "                    dp_helper(j+1, a, b) for a in next_x1\n",
    "                    for b in next_x2\n",
    "                ])\n",
    "            if x1<0 or x1>=len(grid[0]):\n",
    "                pick1=0\n",
    "            else:\n",
    "                pick1 =grid[j][x1]\n",
    "            \n",
    "            if x2<0 or x2>=len(grid[0]):\n",
    "                pick2 =0\n",
    "            \n",
    "            else:\n",
    "                pick2 =grid[j][x2]\n",
    "\n",
    "            if x1!=x2 :\n",
    "                cache[(j,x1,x2)] = pick1 +pick2+next_pick\n",
    "            else:\n",
    "                cache[(j,x1,x2)]= pick1 +next_pick\n",
    "\n",
    "            return cache[(j,x1,x2)]\n",
    "        return dp_helper(0, 0, len(grid[0])-1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def pick(r, c1, c2, dp):\n",
    "            if r == m:\n",
    "                return 0\n",
    "            \n",
    "            if (c1, c2) in dp[r]:\n",
    "                return dp[r][c1,c2]\n",
    "            \n",
    "            t = 0\n",
    "            for dc1 in [-1, 0, 1]:\n",
    "                for dc2 in [-1, 0, 1]:\n",
    "                    nc1, nc2 = dc1 + c1, dc2 + c2\n",
    "                    if not (0 <= nc1 < n and 0 <= nc2 < n):\n",
    "                        continue\n",
    "                    \n",
    "                    ret = pick(r+1, nc1, nc2, dp)\n",
    "                    t = max(t, ret)\n",
    "            \n",
    "            ans = 0\n",
    "            if c1 == c2:\n",
    "                ans = grid[r][c1] + t\n",
    "            else:\n",
    "                ans = grid[r][c1] + grid[r][c2] + t\n",
    "            \n",
    "            dp[r][c1,c2] = ans\n",
    "            return ans\n",
    "        \n",
    "        dp = [{} for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            for i in range(j):\n",
    "                pick(0, i, j, dp)\n",
    "        \n",
    "        return dp[0][0,n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections, functools, heapq, sys\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid) -> int:\n",
    "        if grid[0] == 1:\n",
    "            return sum(x[0] for x in grid)\n",
    "        dx = [-1, -1, -1, 0, 0, 0, 1, 1, 1]\n",
    "        dy = [-1, 0, 1, -1, 0, 1, -1, 0, 1]\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def helper(col, x, y):\n",
    "            if x > y or x < 0 or y >= len(grid[0]): return -sys.maxsize\n",
    "            if col == 0:\n",
    "                return grid[0][0] + grid[0][-1] if x == 0 and y == len(grid[0]) - 1 else -sys.maxsize\n",
    "            if x == y:\n",
    "                cur = grid[col][x]\n",
    "            else:\n",
    "                cur = grid[col][x] + grid[col][y]\n",
    "            return cur + max(helper(col-1, x+dx[i], y+dy[i]) for i in range(9))\n",
    "        ans = 0\n",
    "        for y in range(len(grid[0])):\n",
    "            for x in range(y):\n",
    "                a  =  helper(len(grid)-1,x,y)\n",
    "                ans = max(ans, helper(len(grid)-1,x,y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        # memo = {}\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dp(r1, r2) -> int:\n",
    "            r1i, r1j = r1\n",
    "            r2i, r2j = r2\n",
    "\n",
    "            if r1j < 0 or r1j >= cols or r2j < 0 or r2j >= cols or r1i >= rows or r2i >= rows:\n",
    "                return 0\n",
    "            \n",
    "            if r1j == r2j:\n",
    "                return 0\n",
    "\n",
    "            # if (r1, r2) not in memo:            \n",
    "            return  grid[r1i][r1j] + grid[r2i][r2j] + max([\n",
    "                    dp((r1i + 1, r1j - 1), (r2i + 1, r2j - 1)),\n",
    "                    dp((r1i + 1, r1j - 1), (r2i + 1, r2j)),\n",
    "                    dp((r1i + 1, r1j - 1), (r2i + 1, r2j + 1)),\n",
    "                    dp((r1i + 1, r1j), (r2i + 1, r2j - 1)),\n",
    "                    dp((r1i + 1, r1j), (r2i + 1, r2j)),\n",
    "                    dp((r1i + 1, r1j), (r2i + 1, r2j + 1)),\n",
    "                    dp((r1i + 1, r1j + 1), (r2i + 1, r2j - 1)),\n",
    "                    dp((r1i + 1, r1j + 1), (r2i + 1, r2j)),\n",
    "                    dp((r1i + 1, r1j + 1), (r2i + 1, r2j + 1)),\n",
    "                ])\n",
    "            # return memo[(r1, r2)]\n",
    "\n",
    "        return dp((0,0), (0, cols - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(r,c1,c2):\n",
    "            if r==len(grid) or not (0<=c1<len(grid[0]) and 0<=c2<len(grid[0])):\n",
    "                return 0\n",
    "            ans = grid[r][c1]+grid[r][c2]\n",
    "            if c1==c2:\n",
    "                ans-=grid[r][c1]\n",
    "            newc1 = [c1-1,c1,c1+1]\n",
    "            newc2 = [c2-1,c2,c2+1]\n",
    "            mx = 0\n",
    "            for c11 in newc1:\n",
    "                for c21 in newc2:\n",
    "                    mx = max(mx,dfs(r+1,c11,c21))\n",
    "            return ans+mx\n",
    "        \n",
    "        return dfs(0,0,len(grid[0])-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "        memo = {}\n",
    "\n",
    "        def dp(r1, r2) -> int:\n",
    "            r1i, r1j = r1\n",
    "            r2i, r2j = r2\n",
    "\n",
    "            if r1j < 0 or r1j >= cols or r2j < 0 or r2j >= cols or r1i >= rows or r2i >= rows:\n",
    "                return 0\n",
    "            \n",
    "            if r1j == r2j:\n",
    "                return 0\n",
    "\n",
    "            if (r1, r2) not in memo:            \n",
    "                memo[(r1, r2)] = grid[r1i][r1j] + grid[r2i][r2j] + max([\n",
    "                    dp((r1i + 1, r1j - 1), (r2i + 1, r2j - 1)),\n",
    "                    dp((r1i + 1, r1j - 1), (r2i + 1, r2j)),\n",
    "                    dp((r1i + 1, r1j - 1), (r2i + 1, r2j + 1)),\n",
    "                    dp((r1i + 1, r1j), (r2i + 1, r2j - 1)),\n",
    "                    dp((r1i + 1, r1j), (r2i + 1, r2j)),\n",
    "                    dp((r1i + 1, r1j), (r2i + 1, r2j + 1)),\n",
    "                    dp((r1i + 1, r1j + 1), (r2i + 1, r2j - 1)),\n",
    "                    dp((r1i + 1, r1j + 1), (r2i + 1, r2j)),\n",
    "                    dp((r1i + 1, r1j + 1), (r2i + 1, r2j + 1)),\n",
    "                ])\n",
    "            return memo[(r1, r2)]\n",
    "\n",
    "        return dp((0,0), (0, cols - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dp(i, j1, j2):\n",
    "            if i == m-1: return grid[i][j1] if j1 == j2 else grid[i][j1]+grid[i][j2]\n",
    "            cur = grid[i][j1]+grid[i][j2]\n",
    "            if j1 == j2: cur //= 2\n",
    "            ans = 0\n",
    "            for ni, nj1 in [(i+1, j1-1), (i+1, j1), (i+1, j1+1)]:\n",
    "                if ni < m and 0 <= nj1 < n:\n",
    "                    for nx, nj2 in [(i+1, j2-1), (i+1, j2), (i+1, j2+1)]:\n",
    "                        if nx < m and 0 <= nj2 < n:\n",
    "                            ans = max(ans, cur+dp(ni, nj1, nj2))\n",
    "            return ans\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        return dp(0, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        @functools.cache\n",
    "        def dp(i,j1,j2):\n",
    "            if i == H:\n",
    "                return 0\n",
    "            \n",
    "            return grid[i][j1]+(j1!=j2)*grid[i][j2]+max(dp(i+1,j1,j2) for j1,j2 in itertools.product((j1-1,j1,j1+1),(j2-1,j2,j2+1)) if 0 <= j1 < W and 0 <= j2 < W)\n",
    "        \n",
    "\n",
    "        H,W = len(grid),len(grid[0])\n",
    "        return dp(0,0,W-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#记忆化搜索#\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def  solve(r,c1,c2):\n",
    "            if r==m-1:\n",
    "                return 0\n",
    "            \n",
    "            res=0\n",
    "            for nc1 in range(max(c1-1,0),min(c1+2,n)):\n",
    "                for nc2 in range(max(c2-1,0),min(c2+2,n)):\n",
    "                    if nc1==nc2:\n",
    "                        res=max(res,grid[r+1][nc1]+solve(r+1,nc1,nc2))\n",
    "            \n",
    "                    else:\n",
    "                        res=max(res,grid[r+1][nc1]+grid[r+1][nc2]+solve(r+1,nc1,nc2))\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        ans=solve(0,0,n-1)+grid[0][0]+grid[0][n-1]\n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        # f[i][j][k],在位置[i][j] 机器人k能取得的最多樱桃\n",
    "        # f[i][j][k] = max(f[i-1][j-1][k], f[i-1][j][k], f[i-1][j+1][k]) + grid[i][j]\n",
    "        # 机器人是没有必要交叉的，甚至是没有必要走一个格子，所以各自走一边即可\n",
    "\n",
    "        # 在第i行机器人在j1，机器人2在j2获取的值\n",
    "        def getvalue(i,j1,j2):\n",
    "            return grid[i][j1] + grid[i][j2] \n",
    "        m,n = len(grid),len(grid[0])\n",
    "        @cache\n",
    "        def f(i,j1,j2):\n",
    "            if i == m-1:\n",
    "                return getvalue(i,j1,j2)\n",
    "            res = 0\n",
    "            for dj1 in [j1 - 1, j1, j1 + 1]:\n",
    "                for dj2 in [j2 - 1, j2, j2 + 1]:\n",
    "                    if dj1 < dj2 and 0<= dj1 < n and 0<= dj2 < n:\n",
    "                        res = max(res, f(i+1, dj1, dj2))\n",
    "            return res + getvalue(i,j1,j2)\n",
    "        return f(0,0,n-1)\n",
    "\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(r, c1, c2):\n",
    "            if r == m: return 0\n",
    "            cherries = grid[r][c1] if c1 == c2 else grid[r][c1] + grid[r][c2]\n",
    "            ans = 0\n",
    "            for nc1 in range(c1 - 1, c1 + 2):\n",
    "                for nc2 in range(c2 - 1, c2 + 2):\n",
    "                    if 0 <= nc1 < n and 0 <= nc2 < n:\n",
    "                        ans = max(ans, dfs(r + 1, nc1, nc2))\n",
    "            return ans + cherries\n",
    "\n",
    "        return dfs(0, 0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @staticmethod\n",
    "    def checkValid(grid, pt):\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        x, y = pt[0], pt[1]\n",
    "        if x < 0 or x >= m:\n",
    "            return False \n",
    "        if y < 0 or y >= n: \n",
    "            return False \n",
    "        if grid[x][y] == -1:\n",
    "            return False \n",
    "        return True \n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(p1, p2):\n",
    "            # base case \n",
    "            # NOTE, need to return -float('inf') instead of 0 \n",
    "            if not self.checkValid(grid, p1):\n",
    "                return -float('inf')\n",
    "            if not self.checkValid(grid, p2):\n",
    "                return -float('inf') \n",
    "            # the number of cherries that can be picked up at current position \n",
    "            cherries = 0 \n",
    "            x1, y1 = p1[0], p1[1]\n",
    "            x2, y2 = p2[0], p2[1]\n",
    "            m, n = len(grid), len(grid[0])\n",
    "            cherries += grid[x1][y1]\n",
    "            if not (x1 == x2 and y1 == y2):\n",
    "                cherries += grid[x2][y2]\n",
    "            if x1 == m-1 and x2 == m-1:\n",
    "                return cherries\n",
    "            cherries += max(\n",
    "                dfs((x1+1, y1-1), (x2+1, y2-1)),\n",
    "                dfs((x1+1, y1-1), (x2+1, y2)),\n",
    "                dfs((x1+1, y1-1), (x2+1, y2+1)),\n",
    "                dfs((x1+1, y1), (x2+1, y2-1)),\n",
    "                dfs((x1+1, y1), (x2+1, y2)),\n",
    "                dfs((x1+1, y1), (x2+1, y2+1)),\n",
    "                dfs((x1+1, y1+1), (x2+1, y2-1)),\n",
    "                dfs((x1+1, y1+1), (x2+1, y2)),\n",
    "                dfs((x1+1, y1+1), (x2+1, y2+1)),\n",
    "            )\n",
    "            return cherries\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = dfs((0,0), (0,n-1))\n",
    "        return max(res, 0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(x1,y1,y2):\n",
    "            if x1 == m:\n",
    "                return 0\n",
    "            res = grid[x1][y1]\n",
    "            ans = 0\n",
    "            if y1 != y2:\n",
    "                res += grid[x1][y2]\n",
    "            for py1 in [y1-1,y1,y1+1]:\n",
    "                for py2 in [y2-1,y2,y2+1]:\n",
    "                    if 0 <= py1 < n and 0 <= py2 < n:\n",
    "                        ans = max(ans,dfs(x1+1,py1,py2))\n",
    "            return res+ans\n",
    "        return dfs(0,0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        R, C = len(grid), len(grid[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "\n",
    "        def dfs(r,c1,c2):\n",
    "            if not (0<=c1<C and 1<=c2<C):\n",
    "                return -float(\"inf\")\n",
    "            cur_level_num=grid[r][c1]+grid[r][c2] if c1!=c2 else grid[r][c1]\n",
    "            if r==R-1:\n",
    "                return cur_level_num\n",
    "            max_num=0\n",
    "            for i in [c1-1,c1,c1+1]:\n",
    "                for j in [c2-1,c2,c2+1]:\n",
    "                    max_num=max(max_num,dfs(r+1,i,j))\n",
    "            return max_num+cur_level_num\n",
    "        return dfs(0,0,C-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(x, y, x1, y1):\n",
    "            total = grid[x][y] + grid[x1][y1] if y != y1 else grid[x][y]\n",
    "            if x == m - 1:\n",
    "                return total\n",
    "            res = 0\n",
    "            for i in (y-1, y, y+1):\n",
    "                for j in (y1-1, y1, y1+1):\n",
    "                    if 0 <= i < n and 0 <= j < n:\n",
    "                        res = max(res, dfs(x+1, i, x1+1, j))\n",
    "            return res + total\n",
    "        \n",
    "        return dfs(0, 0, 0, n-1)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def get(px= 0, py=0, qx=0, qy=len(grid[1])-1):\n",
    "            if not 0<=py<len(grid[1]) or not 0 <= qy <len(grid[1]):\n",
    "                return -1e99\n",
    "            if px == qx and py== qy:\n",
    "                to_ret = grid[px][py]\n",
    "            else:\n",
    "                to_ret = grid[px][py] + grid[qx][qy]\n",
    "            if px == len(grid)-1:\n",
    "                return to_ret\n",
    "            max_new = []\n",
    "            for next_py in range(py-1, py+2):\n",
    "                for next_qy in range(qy-1, qy+2):\n",
    "                    max_new.append(get(px+1, next_py, qx+1, next_qy))\n",
    "            return to_ret + max(max_new)\n",
    "        return get()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        @functools.cache\n",
    "        def dfs(i, j1, j2):\n",
    "            if i == m:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for dj1, dj2 in directions:\n",
    "                mj1, mj2 = j1 + dj1, j2 + dj2\n",
    "                if 0 <= mj1 < mj2 < n:  # 最优解一定包含一个在一边走，因为出现交叉后无非是两者交换位置\n",
    "                    res = max(dfs(i + 1, mj1, mj2) + grid[i][j1] + grid[i][j2], res)\n",
    "            return res\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 0], [0, 1], [1, -1], [1, 0], [1, 1]]\n",
    "        return dfs(0, 0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def get_value(i, j1, j2):\n",
    "            if j1 == j2:\n",
    "                return grid[i][j1]\n",
    "            return grid[i][j1] + grid[i][j2]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def  dfs(row, j1, j2):\n",
    "            if row == m-1 :\n",
    "                return get_value(row, j1, j2)\n",
    "            \n",
    "            best = 0\n",
    "            top = min(row+ 2, n)\n",
    "            \n",
    "            for d1 in [j1-1, j1, j1+1]:\n",
    "                for d2 in [j2-1, j2, j2+1]:\n",
    "                    if 0 <= d1 < top and d1<= d2 < n :\n",
    "                        if d2 < n - 2 - row :\n",
    "                            continue\n",
    "                        best = max(dfs(row + 1, d1, d2), best)\n",
    "            \n",
    "            return best + get_value(row, j1, j2 )\n",
    "        \n",
    "        return dfs(0, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        # 填充两个位置免去出界检查\n",
    "        dp = [[0] * (n+2) for _ in range(n+2)]\n",
    "        dp2 = [[0] * (n+2) for _ in range(n+2)]\n",
    "        dp[1][-2] = grid[0][0] + grid[0][-1] # 初始状态\n",
    "        res = 0\n",
    "        for row in range(1, m): # 状态转移次数\n",
    "            for i in range(min(row+1, n)): # 机器人1的行动范围\n",
    "                for j in range(max(i+1, n-row-1), n): # 机器人2的行动范围\n",
    "                    # 机器人2 等于 机器人1 的位置不可能是最大值所以跳过\n",
    "                    # 机器人2 不用走到机器人1 的左边，避免重复计算，有等价状态\n",
    "                    temp = 0\n",
    "                    #上一步走哪个位置，有9种可能，取得最大值,填充两个位置防止出界\n",
    "                    for r1 in [-1, 0, 1]:      # dp[i+1][j+1] 对应 robot1[i]robot2[j] \n",
    "                        for r2 in [-1, 0, 1]:                 \n",
    "                            temp = max(temp, dp[i+1+r1][j+1+r2]) \n",
    "                    dp2[i+1][j+1] = grid[row][i] + grid[row][j] + temp\n",
    "                    # 最后一行求得最大值 \n",
    "                    if row == m - 1: res = max(res, dp2[i+1][j+1])\n",
    "            dp, dp2 = dp2, dp\n",
    "        return res \n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def get_value(i, j1, j2):\n",
    "            if j1 == j2:\n",
    "                return grid[i][j1]\n",
    "            return grid[i][j1] + grid[i][j2]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def  dfs(row, j1, j2):\n",
    "            if j1 > row or j2 < n - row - 1:\n",
    "                return \n",
    "            if row == m-1 :\n",
    "                return get_value(row, j1, j2)\n",
    "            \n",
    "            best = 0\n",
    "            top = min(row+ 2, n)\n",
    "            \n",
    "            for d1 in [j1-1, j1, j1+1]:\n",
    "                for d2 in [j2-1, j2, j2+1]:\n",
    "                    if 0 <= d1 < top and d1<= d2 < n :\n",
    "                        # if d2 < n - 2 - row :\n",
    "                        #     continue\n",
    "                        best = max(dfs(row + 1, d1, d2), best)\n",
    "            \n",
    "            return best + get_value(row, j1, j2 )\n",
    "        \n",
    "        return dfs(0, 0, n-1) \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def get_value(i, j1, j2):\n",
    "            if j1 == j2:\n",
    "                return grid[i][j1]\n",
    "            return grid[i][j1] + grid[i][j2]\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def  dfs(row, j1, j2):\n",
    "            if j1 > row or j2 < n - row - 1:\n",
    "                return \n",
    "            if row == m-1 :\n",
    "                return get_value(row, j1, j2)\n",
    "            \n",
    "            best = 0\n",
    "            #top = min(row+ 2, n)\n",
    "            \n",
    "            for d1 in [j1-1, j1, j1+1]:\n",
    "                for d2 in [j2-1, j2, j2+1]:\n",
    "                    if 0 <= d1 < n and d1<= d2 < n :\n",
    "                        # if d2 < n - 2 - row :\n",
    "                        #     continue\n",
    "                        best = max(dfs(row + 1, d1, d2), best)\n",
    "            \n",
    "            return best + get_value(row, j1, j2 )\n",
    "        \n",
    "        return dfs(0, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        def get(i, j1, j2):\n",
    "            if j1==j2:\n",
    "                return grid[i][j1]\n",
    "            else:\n",
    "                return grid[i][j1] + grid[i][j2]\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j1, j2):\n",
    "            if i == n-1:\n",
    "                return get(i, j1, j2)\n",
    "            \n",
    "            best = 0\n",
    "            for y1 in [j1, j1+1, j1-1]:\n",
    "                for y2 in [j2, j2+1, j2-1]:\n",
    "                    if 0<=y1<m and 0<=y2<m:\n",
    "                        best = max(best, dfs(i+1, y1, y2))\n",
    "            return best + get(i, j1, j2)\n",
    "        \n",
    "        return dfs(0, 0, m-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(pos,x,y):\n",
    "            if pos==n:\n",
    "                return 0\n",
    "            if x>=y:\n",
    "                return 0\n",
    "            res=0\n",
    "            for dx in [-1,0,1]:\n",
    "                if 0 <= x + dx < m:\n",
    "                    for dy in [-1,0,1]:\n",
    "                        if 0<=y+dy<m:\n",
    "                            res=max(res,dfs(pos+1,x+dx,y+dy)+grid[pos][x]+grid[pos][y])\n",
    "            return res\n",
    "\n",
    "\n",
    "        return dfs(0,0,m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(i,j1,j2):\n",
    "            if i==m:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for y1,y2 in product(range(j1-1,j1+2),range(j2-1,j2+2)):\n",
    "                if 0<=y1<n and 0<=y2<n:\n",
    "                    res = max(res, dfs(i+1,y1,y2))\n",
    "            return res+sum(grid[i][j] for j in {j1,j2})\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        return dfs(0,0,n-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j1,j2):\n",
    "            nonlocal m,n\n",
    "            if i == m:\n",
    "                return 0\n",
    "            if j1 == j2:\n",
    "                cur = grid[i][j1]\n",
    "            else:\n",
    "                cur = grid[i][j1] + grid[i][j2]\n",
    "            \n",
    "            maxnum = 0\n",
    "            for nj1 in [j1-1,j1,j1+1]:\n",
    "                if nj1 < 0 or nj1 >= n:\n",
    "                    continue\n",
    "                for nj2 in [j2-1,j2,j2+1]:\n",
    "                    if nj2 < 0 or nj2 >= n or nj2 < nj1:\n",
    "                        continue\n",
    "                    maxnum = max(maxnum, dfs(i+1,nj1,nj2))\n",
    "            \n",
    "            return cur+maxnum\n",
    "        \n",
    "        return dfs(0,0,n-1)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(ii, jj1, jj2):\n",
    "            if ii == m-1:\n",
    "                return grid[ii][jj1] + grid[ii][jj2] if jj1 != jj2 else grid[ii][jj1]\n",
    "\n",
    "            else:\n",
    "                total = grid[ii][jj1] + grid[ii][jj2] if jj1 != jj2 else grid[ii][jj1]\n",
    "\n",
    "                max_val = 0\n",
    "                for new_jj1 in [jj1-1, jj1, jj1+1]:\n",
    "                    for new_jj2 in [jj2-1, jj2, jj2+1]:\n",
    "                        if new_jj1 >= 0 and new_jj1 < n and new_jj2 >= 0 and new_jj2 < n:\n",
    "                            max_val = max(max_val, dp(ii+1, new_jj1, new_jj2))\n",
    "\n",
    "                return total + max_val\n",
    "\n",
    "        return dp(0, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def state(line, x, y):\n",
    "            if line == len(grid) or x < 0 or y >= len(grid[0]) or x >= y: return 0\n",
    "            maxi = 0\n",
    "            for i in range(-1,2):\n",
    "                for j in range(-1,2):\n",
    "                    maxi = max(maxi, state(line+1, x+i, y+j))\n",
    "            # print(line, x ,y)\n",
    "            maxi += grid[line][x]+grid[line][y]\n",
    "            return maxi\n",
    "        return state(0,0,len(grid[0])-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(x1, y1, x2, y2):\n",
    "            if x1 == n - 1:\n",
    "                if y1 != y2: return grid[-1][y1] + grid[-1][y2]\n",
    "                return grid[-1][y1]\n",
    "            res = 0\n",
    "            for nx1, ny1 in (x1 + 1, y1 - 1), (x1 + 1, y1), (x1 + 1, y1 + 1):\n",
    "                if 0 <= nx1 < n and 0 <= ny1 < m:\n",
    "                    for nx2, ny2 in (x2 + 1, y2 - 1), (x2 + 1, y2), (x2 + 1, y2 + 1):\n",
    "                        if 0 <= nx2 < n and 0 <= ny2 < m:\n",
    "                            if dfs(nx1, ny1, nx2, ny2) > res: res = dfs(nx1, ny1, nx2, ny2)\n",
    "            return res + grid[x1][y1] + (grid[x2][y2] if y1 != y2 else 0)\n",
    "        return dfs(0, 0, 0, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y1, y2):\n",
    "            if not (0 <= y1 < n and 0 <= y2 < n and 0 <= x < m):\n",
    "                return 0\n",
    "            cur = grid[x][y1] + grid[x][y2]\n",
    "            if y1 == y2:\n",
    "                cur -= grid[x][y1]\n",
    "            nex = 0\n",
    "            for a in [-1, 0, 1]:\n",
    "                for b in [-1, 0, 1]:\n",
    "                    if dfs(x + 1, y1 + a, y2 + b) > nex:\n",
    "                        nex = dfs(x + 1, y1 + a, y2 + b)\n",
    "            return cur + nex\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        return dfs(0, 0, n - 1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j1, j2):\n",
    "            \n",
    "            cur = grid[i][j1]+grid[i][j2]\n",
    "            if j1 == j2:\n",
    "                cur -= grid[i][j1]\n",
    "            if i == m-1:\n",
    "                return cur\n",
    "            res = -inf\n",
    "            for x1 in [j1-1, j1, j1+1]:\n",
    "                if 0<=x1<n:\n",
    "                    for y1 in [j2-1, j2, j2+1]:\n",
    "                        if 0<=y1<n:\n",
    "                            nex = dfs(i+1, x1, y1)\n",
    "                            if nex > res:\n",
    "                                res = nex\n",
    "            return res + cur\n",
    "        \n",
    "        return dfs(0, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        mem = {}\n",
    "\n",
    "        def get_value(x, y1, y2):\n",
    "            return grid[x][y1] + (grid[x][y2] if y1 != y2 else 0)\n",
    "\n",
    "        def dfs(x, y1, y2):\n",
    "            if x == m - 1:\n",
    "                return get_value(x, y1, y2)\n",
    "            if (x, y1, y2) in mem: return mem[(x, y1, y2)]\n",
    "\n",
    "            res = 0\n",
    "            for new_y1 in [y1 - 1, y1, y1 + 1]:\n",
    "                for new_y2 in [y2 - 1, y2, y2 + 1]:\n",
    "                    if 0 <= new_y1 < n and 0 <= new_y2 < n:\n",
    "                        res = max(res, dfs(x + 1, new_y1, new_y2))\n",
    "\n",
    "\n",
    "            mem[(x, y1, y2)] = res + get_value(x, y1, y2)\n",
    "            return mem[(x, y1, y2)]\n",
    "        \n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        return dfs(0, 0, n - 1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # m, n = len(grid), len(grid[0])\n",
    "        # memo = {}  # 用于存储中间结果的字典\n",
    "\n",
    "        # def getValue(i, j1, j2):\n",
    "        #     return grid[i][j1] + grid[i][j2] if j1 != j2 else grid[i][j1]\n",
    "\n",
    "        # def dfs(i, j1, j2):\n",
    "        #     if i == m - 1:\n",
    "        #         return getValue(i, j1, j2)\n",
    "            \n",
    "        #     if (i, j1, j2) in memo:  # 如果结果已经计算过，直接返回\n",
    "        #         return memo[(i, j1, j2)]\n",
    "            \n",
    "        #     best = 0\n",
    "        #     for dj1 in [j1 - 1, j1, j1 + 1]:\n",
    "        #         for dj2 in [j2 - 1, j2, j2 + 1]:\n",
    "        #             if 0 <= dj1 < n and 0 <= dj2 < n:\n",
    "        #                 best = max(best, dfs(i + 1, dj1, dj2))\n",
    "\n",
    "        #     memo[(i, j1, j2)] = best + getValue(i, j1, j2)  # 存储计算结果\n",
    "        #     return memo[(i, j1, j2)]\n",
    "        \n",
    "        # return dfs(0, 0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        def getValue(i, j1, j2):\n",
    "            return grid[i][j1] + grid[i][j2] if j1 != j2 else grid[i][j1]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j1, j2):\n",
    "            if i == m - 1:\n",
    "                return getValue(i, j1, j2)\n",
    "\n",
    "            best = 0\n",
    "            for dj1 in [j1 - 1, j1, j1 + 1]:\n",
    "                for dj2 in [j2 - 1, j2, j2 + 1]:\n",
    "                    if 0 <= dj1 < n and 0 <= dj2 < n:\n",
    "                        best = max(best, dfs(i + 1, dj1, dj2))\n",
    "\n",
    "            return best + getValue(i, j1, j2)\n",
    "        \n",
    "        return dfs(0, 0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        # 返回从i层开始到最后一层能摘取的最多的樱桃\n",
    "        def f(i, j1, j2):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            t = 0\n",
    "            for jj1 in range(j1 - 1, j1 + 2):\n",
    "                for jj2 in range(j2 - 1, j2 + 2):\n",
    "                    if 0 <= jj1 < m and 0 <= jj2 < m:\n",
    "                        t = max(f(i+1, jj1, jj2), t)\n",
    "            if j1 == j2:\n",
    "                return grid[i][j1] + t\n",
    "            return grid[i][j1] + grid[i][j2] + t\n",
    "        return f(0, 0, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        @cache \r\n",
    "        def dfs(i, c1, c2) -> int:\r\n",
    "            if i == m:\r\n",
    "                return 0 \r\n",
    "            res = 0\r\n",
    "            for x in range(max(0, c1 - 1), min(c1 + 2, n)):\r\n",
    "                for y in range(max(0, c2 - 1), min(c2 + 2, n)):\r\n",
    "                    res = max(res, dfs(i + 1, x, y))\r\n",
    "            if c1 == c2:\r\n",
    "                return res + grid[i][c1] \r\n",
    "            else:\r\n",
    "                return res + grid[i][c1] + grid[i][c2] \r\n",
    "        return dfs(0, 0, n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        dx, dy = [1, 1, 1], [-1, 0, 1]\n",
    "        @cache\n",
    "        def dfs(x, y1, y2):\n",
    "            if x >= n: return 0\n",
    "            res = -inf\n",
    "            for i in range(3):\n",
    "                for j in range(3):\n",
    "                    ny1, ny2 = y1 + dy[i], y2 + dy[j]\n",
    "                    if 0 <= ny1 < m and 0 <= ny2 < m:\n",
    "                        if y1 != y2:\n",
    "                            res = max(res, dfs(x + 1, ny1, ny2) + grid[x][y1] + grid[x][y2])\n",
    "                        else:\n",
    "                            res = max(res, dfs(x + 1, ny1, ny2) + grid[x][y1])\n",
    "            return res\n",
    "        return dfs(0, 0, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid), len(grid[0])\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def get_value(i, j1,j2):\n",
    "            return grid[i][j1] if j1 == j2 else grid[i][j1] + grid[i][j2]\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(i,j1,j2):\n",
    "            if i == m-1:\n",
    "                return get_value(i,j1,j2)\n",
    "            post = 0\n",
    "            for k1 in [j1-1,j1,j1+1]:\n",
    "                for k2 in [j2-1,j2,j2+1]:\n",
    "                    if 0<=k1<n and 0<=k2<n:\n",
    "                        post = max(post, dp(i+1,k1,k2))\n",
    "            return get_value(i,j1,j2) + post\n",
    "\n",
    "        return dp(0,0,n-1)\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        memo = {}\n",
    "        def dfs(i, j, x, y):\n",
    "            if (i, j, x, y) in memo:\n",
    "                return memo[(i, j, x, y)]\n",
    "            if i == x == m:\n",
    "                return 0\n",
    "            if j < 0 or j >= n or y < 0 or y >= n:\n",
    "                return float('-inf')\n",
    "            res = 0 # float('-inf')\n",
    "            for di, dj in [(1, -1), (1, 0), (1, 1)]:\n",
    "                for dx, dy in [(1, -1), (1, 0), (1, 1)]:\n",
    "                   \n",
    "                    # res += is wrong. must use max logic\n",
    "                    if (i, j) == (x, y): # important curr val is for i, j x, y not ni, nj, nx ,ny\n",
    "                        val = grid[i][j]\n",
    "                    else:\n",
    "                        val = grid[i][j] + grid[x][y] \n",
    "                    ni, nj = i + di, j + dj\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    res = max(res, dfs(ni, nj, nx, ny) + val)\n",
    "            memo[(i, j, x, y)] = res\n",
    "            return res\n",
    "        return dfs(0, 0, 0, n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        direct=[-1,0,1]\n",
    "        @cache\n",
    "        def dfs(x,y1,y2):\n",
    "            if x>=m or y1<0 or y2<0 or y1>=n or y2>=n:\n",
    "                return 0\n",
    "            ans=0\n",
    "            if y1==y2:\n",
    "                reward=grid[x][y1]\n",
    "                grid[x][y1]=0\n",
    "                for i in direct:\n",
    "                    for j in direct:\n",
    "                        ans=max(ans,dfs(x+1,y1+i,y2+j)+reward)\n",
    "                grid[x][y1]=reward\n",
    "                return ans                        \n",
    "            else:\n",
    "                reward1=grid[x][y1]\n",
    "                reward2=grid[x][y2]\n",
    "                grid[x][y1]=0\n",
    "                grid[x][y2]=0\n",
    "                for i in direct:\n",
    "                    for j in direct:\n",
    "                        ans=max(ans,dfs(x+1,y1+i,y2+j)+reward1+reward2)\n",
    "                grid[x][y1]=reward1\n",
    "                grid[x][y2]=reward2\n",
    "                return ans             \n",
    "        return dfs(0,0,n-1)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i,j1,j2):\n",
    "            if i== m:\n",
    "                return 0\n",
    "            if j1 < 0 or j1 == n or j2 < 0 or j2 == n:\n",
    "                return 0\n",
    "            t = 0\n",
    "            if j1 == j2:\n",
    "                t = grid[i][j1]\n",
    "            else:\n",
    "                t = grid[i][j1] + grid[i][j2]\n",
    "            ans = 0\n",
    "            for j in (-1,0,1):\n",
    "                for k in (-1,0,1):\n",
    "                    ans = max(ans,t + dfs(i + 1,j1 + j,j2 + k))\n",
    "            return ans\n",
    "        return dfs(0,0,n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, a, b):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            if a < 0 or a >= m or b < 0 or b >= m:\n",
    "                return -inf\n",
    "            if a != b:\n",
    "                res = grid[i][a] + grid[i][b]\n",
    "            else:\n",
    "                res = grid[i][a]\n",
    "            tot = 0\n",
    "            for k in range(-1, 2):\n",
    "                for t in range(-1, 2):\n",
    "                    tot = max(tot, dfs(i + 1, a + k, b + t))\n",
    "            return res + tot\n",
    "\n",
    "        return dfs(0, 0, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\r\n",
    "        n, m = len(grid), len(grid[0])\r\n",
    "        \r\n",
    "        @cache\r\n",
    "        def dfs(x1,y1,x2,y2):\r\n",
    "            if not (0 <= x1 < n and 0 <= x2 < n and 0 <= y1 < m and 0 <= y2 < m):\r\n",
    "                return float('-inf')\r\n",
    "            if x1 == n - 1:\r\n",
    "                return grid[x1][y1] if (x1, y1) == (x2, y2) else grid[x1][y1] + grid[x2][y2]\r\n",
    "            ans = 0\r\n",
    "            if (x1, y1) == (x2, y2):\r\n",
    "                ans += grid[x1][y1]\r\n",
    "            else:\r\n",
    "                ans += grid[x1][y1] + grid[x2][y2]\r\n",
    "            ans += max(\r\n",
    "                dfs(x1+1,y1,x2+1,y2-1),\r\n",
    "                dfs(x1+1,y1,x2+1,y2),\r\n",
    "                dfs(x1+1,y1,x2+1,y2+1),\r\n",
    "                dfs(x1+1,y1+1,x2+1,y2-1),\r\n",
    "                dfs(x1+1,y1+1,x2+1,y2),\r\n",
    "                dfs(x1+1,y1+1,x2+1,y2+1),\r\n",
    "                dfs(x1+1,y1-1,x2+1,y2-1),\r\n",
    "                dfs(x1+1,y1-1,x2+1,y2),\r\n",
    "                dfs(x1+1,y1-1,x2+1,y2+1),\r\n",
    "            )\r\n",
    "            return ans\r\n",
    "        return dfs(0,0,0,m-1)\r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(a,b,c,d):\n",
    "            # print(a,b,c,d)\n",
    "            if a==m:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            for nb in (b-1,b,b+1):\n",
    "                if nb<0 or nb>=n:\n",
    "                    continue\n",
    "                for nd in (d-1,d,d+1):\n",
    "                    if nd<0 or nd>=n:\n",
    "                        continue\n",
    "                    # print(a+1,nb,c+1,nd)\n",
    "                    ans = max(ans, (grid[a][b] + grid[c][d] if b!=d else grid[a][b]) + dfs(a+1,nb,c+1,nd))\n",
    "            return ans\n",
    "        return dfs(0,0,0,n-1)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cherryPickup(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(x1, y1, x2, y2):\n",
    "            if not (0 <= x1 < n and 0 <= y1 < m and 0 <= x2 < n and 0 <= y2 < m): # 越界，返回负无穷\n",
    "                return -float('inf')\n",
    "            if grid[x1][y1] == -1 or grid[x2][y2] == -1: # 走到障碍上，返回负无穷\n",
    "                return -float('inf')\n",
    "            res = 0\n",
    "            if x1 != x2 or y1 != y2: # 两个人走到不同位置，把两个位置的樱桃都吃掉\n",
    "                res += grid[x1][y1] + grid[x2][y2]\n",
    "            elif grid[x1][y1]: # 两个人走到相同位置，当前位置有樱桃，则只能吃到1个\n",
    "                res += grid[x1][y1]\n",
    "            if x1 == n - 1 and x2 == n - 1: # 搜索的终止条件\n",
    "                return res\n",
    "            res += max(dfs(x1 + 1, y1 - 1, x2 + 1, y2 - 1), dfs(x1 + 1, y1 - 1, x2 + 1, y2), dfs(x1 + 1, y1 - 1, x2 + 1, y2 + 1), dfs(x1 + 1, y1, x2 + 1, y2 - 1), dfs(x1 + 1, y1, x2 + 1, y2), dfs(x1 + 1, y1, x2 + 1, y2 + 1), dfs(x1 + 1, y1 + 1, x2 + 1, y2 - 1), dfs(x1 + 1, y1 + 1, x2 + 1, y2), dfs(x1 + 1, y1 + 1, x2 + 1, y2 + 1))\n",
    "            return res\n",
    "            \n",
    "        return max(dfs(0, 0, 0, m - 1), 0) # 如果只能走到障碍上或越界那就会返回负无穷，所以要跟0取max\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
